package cn.fxzhang.leetcode.no09;

import cn.fxzhang.leetcode.common.TreeNode;

/**
 * 938. 二叉搜索树的范围和
 * 给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。
 * 提示：
 * 树中节点数目在范围 [1, 2 * 10^4] 内
 * 1 <= Node.val <= 10^5
 * 1 <= low <= high <= 10^5
 * 所有 Node.val 互不相同
 *
 * 类型：二叉树
 * 题解：递推
 * 时间复杂度：O(N)
 * 空间复杂度：O(N)
 *
 * 提交记录(1/1)：
 * 执行用时: 0 ms, 击败了100.00%
 * 内存消耗: 46.4 MB, 击败了76.33%
 *
 * 【中等】通过次数116,961提交次数267,848
 * @author 张晓帆
 * @date 2021/3/30
 */
public class P0938_Range_Sum_Of_Bst {

    public int rangeSumBST(TreeNode root, int low, int high) {
        if (root == null){
            return 0;
        }
        int sum = 0;
        if (root.val >= low && root.val <= high){
            sum += root.val;
        }
        if (root.val > low){
            sum += rangeSumBST(root.left, low, high);
        }
        if (root.val < high){
            sum += rangeSumBST(root.right, low, high);
        }
        return sum;
    }
}
